package com.fantsey.test.juejin;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 问题描述
 * 给定一个长度为n的整型数组，已知其中一个数字的出现次数超过数组长度的一半，找出这个元素
 * 输入格式
 * 一个长度为n的数组，其中某个元素的出现次数大于n/2
 * 输出格式
 * 一个整数
 * 输入样例
 * [1,3,8,2,3,1,3,3,3]
 * 输出样例
 * 3
 *
 * @author fx
 * @date 2025/1/3
 * @since 1.0
 */
public class Question8 {

    public static int solution(int[] array) {
        // Edit your code here
        Map<Integer, Integer> numberCountMap = new HashMap<>(16);
        for (int i : array) {
            numberCountMap.put(i, numberCountMap.getOrDefault(i, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : numberCountMap.entrySet()) {
            Integer value = entry.getValue();
            if (value > array.length/2) {
                return entry.getKey();
            }
        }
        throw new IllegalArgumentException("No majority element found");
    }


    public static void main(String[] args) {
        // Add your test cases here

        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3);
    }
}
